SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bounds checking</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Bounds checking</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computer_programming" title="Computer programming">computer programming</a>, <b>bounds checking</b> is any method of detecting whether a <a href="Variable_(programming)" class="mw-redirect" title="Variable (programming)">variable</a> is within some <a href="Upper_and_lower_bounds" title="Upper and lower bounds">bounds</a> before it is used. It is usually used to ensure that a number fits into a given type (range checking), or that a variable being used as an <a href="Array_data_structure" class="mw-redirect" title="Array data structure">array</a> index is within the bounds of the array (index checking). A failed bounds check usually results in the generation of some sort of <a href="Exception_handling" title="Exception handling">exception</a> signal.

</p><p>As performing bounds checking during each use can be time-consuming, it is not always done. <a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a> is a <a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">compiler optimization</a> technique that eliminates unneeded bounds checking.

</p>

<div class="mw-heading mw-heading2"><h2 id="Range_checking">Range checking</h2></div>

<p>A range check is a check to make sure a number is within a certain range; for example, to ensure that a value about to be assigned to a 16-bit integer is within the capacity of a 16-bit integer (i.e. checking against <a href="Arithmetic_overflow" class="mw-redirect" title="Arithmetic overflow">wrap-around</a>). This is not quite the same as <a href="Type_checking" class="mw-redirect" title="Type checking">type checking</a>. Other range checks may be more restrictive; for example, a variable to hold the number of a calendar month may be declared to accept only the range 1 to 12.

</p><p>Example in <a href="Python_(programming_language)" title="Python (programming language)">Python</a>:

</p>

<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre><span class="k">def</span><span class="w"> </span><span class="nf">set_month</span><span class="p">(</span><span class="n">month</span><span class="p">:</span> <span class="nb">int</span><span class="p">):</span>

<span class="k">if</span> <span class="n">month</span> <span class="o"><</span> <span class="mi">1</span> <span class="ow">or</span> <span class="n">month</span> <span class="o">></span> <span class="mi">12</span><span class="p">:</span>

<span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">"The month must be between 1 and 12"</span><span class="p">)</span>

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Index_checking">Index checking</h2></div>

<p>Index checking means that, in all <a href="Expression_(programming)" class="mw-redirect" title="Expression (programming)">expressions</a> indexing an array, the index value is checked against the bounds of the array (which were established when the array was defined), and if the index is out-of-bounds, further execution is suspended via some sort of error. Because reading or especially writing a value outside the bounds of an array may cause the program to malfunction or crash or enable security vulnerabilities (see <a href="Buffer_overflow" title="Buffer overflow">buffer overflow</a>), index checking is a part of many <a href="High-level_programming_language" title="High-level programming language">high-level languages</a>.

</p><p>Early compiled <a href="Programming_language" title="Programming language">programming languages</a> with index checking ability included <a href="ALGOL_60" title="ALGOL 60">ALGOL 60</a>, <a href="ALGOL_68" title="ALGOL 68">ALGOL 68</a> and <a href="Pascal_(programming_language)" title="Pascal (programming language)">Pascal</a>, as well as interpreted programming languages such as <a href="BASIC" title="BASIC">BASIC</a>.

</p><p>Many programming languages, such as <a href="C_(programming_language)" title="C (programming language)">C</a>, never perform automatic bounds checking to raise speed. However, this leaves many <a href="Off-by-one_error" title="Off-by-one error">off-by-one errors</a> and <a href="Buffer_overflow" title="Buffer overflow">buffer overflows</a> uncaught. Many programmers believe these languages sacrifice too much for rapid execution.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In his 1980 <a href="Turing_Award" title="Turing Award">Turing Award</a> lecture, <a href="C._A._R._Hoare" class="mw-redirect" title="C. A. R. Hoare">C. A. R. Hoare</a> described his experience in the design of <a href="ALGOL_60" title="ALGOL 60">ALGOL 60</a>, a language that included bounds checking, saying:

</p>

<blockquote><p>A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interest of efficiency on production runs. Unanimously, they urged us not to—they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law.</p></blockquote>

<p>Mainstream languages that enforce run time checking include <a href="Ada_(programming_language)" title="Ada (programming language)">Ada</a>, <a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a>, <a href="Haskell_(programming_language)" class="mw-redirect" title="Haskell (programming language)">Haskell</a>, <a href="Java_(programming_language)" title="Java (programming language)">Java</a>, <a href="JavaScript" title="JavaScript">JavaScript</a>, <a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a>, <a href="PHP" title="PHP">PHP</a>, <a href="Python_(programming_language)" title="Python (programming language)">Python</a>, <a href="Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a>, <a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a>, and <a href="Visual_Basic" title="Visual Basic">Visual Basic</a>. The <a href="D_(programming_language)" title="D (programming language)">D</a> and <a href="OCaml" title="OCaml">OCaml</a> languages have run time bounds checking that is enabled or disabled with a compiler switch. In <a href="C%2B%2B" title="C++">C++</a> run time checking is not part of the language, but part of the <a href="Standard_Template_Library" title="Standard Template Library">STL</a> and is enabled with a compiler switch (_GLIBCXX_DEBUG=1 or _LIBCPP_DEBUG=1). C# also supports <i>unsafe regions</i>: sections of code that (among other things) temporarily suspend bounds checking to raise efficiency. These are useful for speeding up small time-critical bottlenecks without sacrificing the safety of a whole program.

</p><p>The <a href="JS%2B%2B" title="JS++">JS++</a> programming language is able to analyze if an array index or map key is out-of-bounds at compile time using existent types, which is a <a href="Nominal_type_system" title="Nominal type system">nominal type</a> describing whether the index or key is within-bounds or out-of-bounds and guides code generation. Existent types have been shown to add only <span class="clarify-content" style="padding-left:0.1em; padding-right:0.1em; color:var(--color-subtle, #54595d); border:1px solid var(--border-color-subtle, #c8ccd1);">1ms overhead</span> to compile times.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Hardware_bounds_checking">Hardware bounds checking</h2></div>

<p>The safety added by bounds checking necessarily costs CPU time if the checking is performed in software; however, if the checks could be performed by hardware, then the safety can be provided "for free" with no runtime cost. An early system with hardware bounds checking was the <a href="ICL_2900_Series" title="ICL 2900 Series">ICL 2900 Series</a> mainframe announced in 1974.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The <a href="VAX" title="VAX">VAX</a> computer has an INDEX assembly instruction for array index checking which takes six operands, all of which can use any VAX addressing mode. The B6500 and similar <a href="Burroughs_Corporation" title="Burroughs Corporation">Burroughs</a> computers performed bound checking via hardware, irrespective of which computer language had been compiled to produce the machine code. A limited number of later <a href="CPU" class="mw-redirect" title="CPU">CPUs</a> have specialised instructions for checking bounds, e.g., the CHK2 instruction on the <a href="Motorola_68000#Interrupts" title="Motorola 68000">Motorola 68000</a> series.

</p><p>Research has been underway since at least 2005 regarding methods to use x86's built-in virtual memory management unit to ensure safety of array and buffer accesses.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> In 2015 Intel provided their <a href="Intel_MPX" title="Intel MPX">Intel MPX</a> extensions in their <a href="Skylake_(microarchitecture)" title="Skylake (microarchitecture)">Skylake</a> processor architecture which stores bounds in a CPU register and table in memory. As of early 2017 at least <a href="GNU_Compiler_Collection" title="GNU Compiler Collection">GCC</a> supports MPX extensions.

</p>

<ul><li><a href="Dynamic_code_analysis" class="mw-redirect" title="Dynamic code analysis">Dynamic code analysis</a></li>

<li><a href="Runtime_error_detection" title="Runtime error detection">Runtime error detection</a></li>

<li><a href="Static_program_analysis" title="Static program analysis">Static code analysis</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCowanWagleCalton_PuBeattie1999" class="citation book cs1">Cowan, C; Wagle, F; Calton Pu; Beattie, S; Walpole, J (1999). "Buffer overflows: Attacks and defenses for the vulnerability of the decade". <i>Proceedings DARPA Information Survivability Conference and Exposition. DISCEX'00</i>. Vol. 2. pp. <span class="nowrap">119–</span>129. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FDISCEX.2000.821514">10.1109/DISCEX.2000.821514</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7695-0490-2</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:167759976">167759976</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20190112060200/https://www.onux.com/jspp/blog/jspp-0-9-0-efficient-compile-time-analysis-of-out-of-bounds-errors/">"JS++ 0.9.0: Efficient Compile Time Analysis of Out-of-Bounds Errors – JS++ Blog"</a>. 11 January 2019. Archived from <a rel="nofollow" class="external text" href="https://www.onux.com/jspp/blog/jspp-0-9-0-efficient-compile-time-analysis-of-out-of-bounds-errors/">the original</a> on 2019-01-12.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFJ._K._Buckle1978" class="citation book cs1">J. K. Buckle (1978). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180420203006/http://www.fujitsu.com/uk/Images/icl-2900-series-by-jk-buckle.pdf"><i>The ICL 2900 Series</i></a> <span class="cs1-format">(PDF)</span>. Macmillan Computer Science Series. pp. 17, 77. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-333-21917-1</bdi>. Archived from <a rel="nofollow" class="external text" href="http://www.fujitsu.com/uk/Images/icl-2900-series-by-jk-buckle.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 20 April 2018<span class="reference-accessdate">. Retrieved <span class="nowrap">20 April</span> 2018</span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFLap-Chung_LamTzi-Cker_Chiueh2005" class="citation book cs1">Lap-Chung Lam; Tzi-Cker Chiueh (2005). "Checking Array Bound Violation Using Segmentation Hardware". <i>2005 International Conference on Dependable Systems and Networks (DSN'05)</i>. pp. <span class="nowrap">388–</span>397. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FDSN.2005.25">10.1109/DSN.2005.25</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7695-2282-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6278708">6278708</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>“<a rel="nofollow" class="external text" href="https://web.archive.org/web/20160623195112/http://www.feustel.us/Feustel%20%26%20Associates/Advantages.pdf">On The Advantages Of Tagged Architecture</a>”, IEEE Transactions On Computers, Volume C-22, Number 7, July, 1973.</li>

<li>“<a rel="nofollow" class="external text" href="http://zoo.cs.yale.edu/classes/cs422/2011/bib/hoare81emperor.pdf">The Emperor’s Old Clothes</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20171002195604/http://zoo.cs.yale.edu/classes/cs422/2011/bib/hoare81emperor.pdf">Archived</a> 2017-10-02 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>”, The 1980 ACM Turing Award Lecture, CACM volume 24 number 2, February 1981, pp 75–83.</li>

<li>“<a rel="nofollow" class="external text" href="https://www.doc.ic.ac.uk/~afd/rarepapers/KendallBccRuntimeCheckingsforC.pdf">Bcc: Runtime checking for C programs</a>”, Samuel C. Kendall, Proceedings of the <a href="USENIX" title="USENIX">USENIX</a> Summer 1983 Conference.</li>

<li>“<a rel="nofollow" class="external text" href="https://web.archive.org/web/20160326081542/https://www.doc.ic.ac.uk/~phjk/BoundsChecking.html">Bounds Checking for C</a>”, Richard Jones and Paul Kelly, Imperial College, July 1995.</li>

<li>“<a rel="nofollow" class="external text" href="https://web.archive.org/web/20130124070111/http://public.support.unisys.com/aseries/docs/clearpath-mcp-11.0/pdf/38347639-000.pdf">ClearPath Enterprise Servers MCP Security Overview</a>”, Unisys, April 2006.</li>

<li>“<a rel="nofollow" class="external text" href="http://llvm.org/pubs/2007-SOSP-SVA.pdf">Secure Virtual Architecture: A Safe Execution Environment for Commodity Operating Systems</a>”, John Criswell, Andrew Lenharth, Dinakar Dhurjati, Vikram Adve, SOSP'07 21st ACM Symposium on Operating Systems Principles, 2007.</li>

<li>“<a rel="nofollow" class="external text" href="https://web.archive.org/web/20160707163127/https://staff.aist.go.jp/y.oiwa/FailSafeC/index-en.html">Fail-Safe C</a>”, Yutaka Oiwa. Implementation of the Memory-safe Full ANSI-C Compiler. ACM SIGPLAN Conference on Programing Language Design and Implementations (PLDI2009), June 2009.</li>

<li>“<a rel="nofollow" class="external text" href="https://github.com/google/sanitizers/wiki/AddressSanitizer">address-sanitizer</a>”, Timur Iskhodzhanov, Alexander Potapenko, Alexey Samsonov, Kostya Serebryany, Evgeniy Stepanov, Dmitriy Vyukov, LLVM Dev Meeting, November 18, 2011.</li>

<li><a rel="nofollow" class="external text" href="https://sourceforge.net/projects/safeclib/">Safe C Library of Bounded APIs</a></li>

<li><cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131202222313/http://www.drdobbs.com/cpp/the-safe-c-library/214502214">"The Safe C Library"</a>. <i><a href="Dr._Dobb's_Journal" title="Dr. Dobb's Journal">Dr. Dobb's Journal</a></i>. February 20, 2009. Archived from <a rel="nofollow" class="external text" href="http://www.drdobbs.com/cpp/the-safe-c-library/214502214">the original</a> on December 2, 2013<span class="reference-accessdate">. Retrieved <span class="nowrap">November 13,</span> 2012</span>.</cite></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131203031224/http://www.owasp.org.cn/OWASP_Conference/2011/17_.pdf">Safe C API—Concise solution of buffer overflow, The OWASP Foundation, OWASP AppSec, Beijing 2011 </a></li>

<li><a rel="nofollow" class="external text" href="https://gcc.gnu.org/onlinedocs/libstdc++/manual/using_macros.html">The GNU C++ Library Manual Macros</a></li>

<li><a rel="nofollow" class="external text" href="https://libcxx.llvm.org/docs/DesignDocs/DebugMode.html">libc++ 11.0 documentation Debug Mode</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-15" href="https://en.wikipedia.org/wiki/?title=Bounds_checking&oldid=1275899253">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>